// https://leetcode.cn/problems/3sum/

// 题干：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
//      满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0
//      请你返回所有和为 0 且不重复的三元组。

// 示例：输入：nums = [-1,0,1,2,-1,-4]
//       输出：[[-1,-1,2],[-1,0,1]]

// 碎语：本质上与两数之和无异，都是先固定再选数，只是繁琐些
//       有意思的地方在于去重，实际上，去重的思路除了先选再删，还能像本题的边选边删

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        // 先排序，便于后续操作
        sort(nums.begin(), nums.end());

        vector<vector<int>> ret;
        for (int i = nums.size() - 1 ; i >= 2 ; ){
            int target = -nums[i]; // a,b之和
            int left = 0, right = i - 1;

            while (left < right) { // 注意是小于和不等于的区别
                if (nums[left] + nums[right] > target) right--;
                else if (nums[left] + nums[right] < target) left++;
                else { // 这个时候，a+b+c=0，注意去重
                    ret.push_back({nums[left], nums[right], nums[i]});

                    // 找到了一个，这时候left和right都要移动，因为若只移动一个，必然重复
                    left++, right--;

                    // 各判断左右两指针移动后是否仍指向同一个值，注意不要越界
                    while (left < right && nums[left] == nums[left - 1]){
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]){
                        right--;
                    }
                }
            }

            // 出了指针循环，这时候i变化，可i的变化可能不是逐渐递减的，因此拉到循环里面操控
            // 相应的，删掉for循环里面的i自减
            i--;
            while (i >= 2 && nums[i] == nums[i + 1]){
                i--;
            }
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {-1,0,1,2,-1,-4};

    vector<vector<int>> index = sol.threeSum(nums);
    for (const auto& arr : index){
        for (int num : arr){
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}
